// hard

// 给定一个数组nums，nums是升序数组经过旋转得到的，但是旋转次数未知，数组中可能存在重复元素
// 要求找出数组中的最小元素

// 思路1： 二分查找
// 数组经过旋转后会有两种情况：1. 原先的升序序列， 2. 两端升序的序列
// 第一种的最小值在最左边， 第二种最小值在第二段升序序列的第一个元素
// left，right两个指针分别指向 数组的首尾，然后计算指针中间值mid，将mid与两指针比较
// 如果nums[mid] > nums[right],则最小值不可能在mid左侧，一定在mid右侧，将left移动到mid+1位置，继续查找右侧区间
// 如果nums[mid] <= nums[right],则最小值一定在mid左侧，将right移动到mid位置上，继续查找左侧区间
// 如果nums[mid] === nums[right],无法判断在mid哪一侧，可以采用right = right - 1，逐步缩小区域

function findMin(nums) {
    let left = 0
    let right = nums.length - 1
    while (left < right) {
        let mid = left + Math.floor((right - left) / 2)
        if (nums[mid] > nums[right]) {
            left = mid + 1
        } else if (nums[mid] < nums[right]) {
            right = mid
        } else {
            right = right - 1
        }
    }
    return nums[left]
}

let arr = [3, 4, 5, 1, 2, 2, 3]
console.log(findMin(arr));